Diary

Just random thoughts.

The content of this page is highly volatile. I don't want to give each day and each thought a permalink. Some of these thoughts may grow to articles, some never won't. Thus, comments and webmentions will never be implemented for this page. But for archived pages, well, they might be.

Archives

2026-09

2026-10-07

Back online again and seem to be still alive.

As I heard in The Magnificent Century series Allah takes our souls when we're asleep and brings them back when we're about to wake. That's in line with Westworld. Muslims knew something.

♡♡♡

When did I decide to revise PetWay memory model at a whole and allocator in particular?

It was mid-July.

Summer is not good time for coding. It's a good time for living.

Unless you're up to organized slavery.

The outcome is no outcome for these three months. But I see the end of the road!

Let's go, bodhisattva!

♡♡♡

As a reminder for myself: move all existing file I/O to blocking subdirectory. That will be self-explaining.

If someone implemented a brand new operating system today from scratch (me, for example), it would be fully asynchronous.

But in the reign of LLMs I doubt anyone is capable of desinging the API. Only a few, maybe. If they are still alive.

2026-10-06

Why am I writing this bullshit? Notes for the documentation? Anyway, let it be.

Basically, realloc can be implemented as

void* realloc(void* addr, unsigned old_size, unsigned new_size)
{
    void* new_addr = alloc(new_size);
    memcpy(new_addr, addr, old_size);
    free(addr, old_size);
    return new_addr;
}

The problem is memcpy that should be avoided.

Then realloc splits into optimized grow and shrink. When optimization fails, memcpy is unavoidable.

In PetWay, the allocator does not track the size of allocated blocks. It's a controversial design decision, but adding even 32-bit unsigned to each allocated block is too wasteful. Its width is close to an average size of English word, not even mentioning the width of size_t on 64-bit systems.

So, realloc and free have old_size argument. Really, I haven't seen a situation where the caller was unable to quickly and reliably get old_size. Oh, yes, C strings. But their only purpose is POSIX API. That extreme case can be worked around.

The allocator uses unsigned instead of size_t. Need memory blocks bigger than 4GB? mmap is the best choice then. Do it youself, in other words. Embracing that extreme case and use size_t in the allocator API does not look good.

Finally, realloc and free actually accept a pointer to pointer:

bool realloc(void** addr_ptr, unsigned old_size, unsigned new_size);
void free(void** addr_ptr, unsigned size);

That's just a precaution against reusing invalid address and double free. However, C language is still dangerous because compilers typically see no difference between void* and void**. The only advantage of void** is catching segfault early instead of double free.

Normally, the use of allocator API should be limited by implementation of strings and storage types such as arrays, maps, lists, etc.

Just looked at most awful code of some open source projects. I won't tell which ones, the point is they all try to localize memory allocation. The worst case is a wrapper around vprintf. If they had normal string API they wouldn't have to call malloc/free in a loop.

Zig scares me each time I see something written in it. Wherever I look I see allocator parameter.

Someone posted on lobsters recently how they dragged that allocator throughout the code to make things working. Another guy asked an LLM for them for a better solution. Yuck!

No, allocator must be invisible. But it must be replaceable.

In PetWay each page header starts with a pointer to allocator. Simply because the allocator contains page catalog.

The allocator is selected in alloc function which has the following prototype:

void* alloc(unsigned size, bool clean, void* shmem);

It's shmem argument. Naming is not perfect as usual, but I can't do better.

shmem can be one of predefined constants to select allocator explicitly or it can point to an existing memory block to use the same allocator. The default allocator is thread-local that does not require any synchronization at all.

Time to draw a big picture?

🤔🤔🤔

Fucked up again. A flaw in allocator design(?) is spotted by complexity of grow function. As I said, grow is an optimization for realloc and premature optimization is the root of all evil, but in this case it's is not quite true.

The problem is that the very first small page of allocated big page contains page header. It either contains a bitmap or the number of big pages in the block.

Too many execution paths already.

The real evil is that very first page can be handed to sub-allocator. The header is quite small and wasting almost 4 KiB is not a good idea. That's normal for small allocations when pages in a big page are managed with bitmap. That big page is a container that never moves. But what if we deal with a really big block and need to remap it to a different address?

We cannot move it if the first page is already in use.

I missed this point.

I need to revise alignment rules.

Why alignment?

Alignment is a key to locate allocator structures. The idea seems to be neither original nor new. I came to it by myself, but later I've seen other projects that use it.

Addresses returned by allocator may lay in different allocation regions. Very small blocks are managed by the bitmap sub-allocator which in turn request pages from the page allocator.

Every page used by sub-allocator contains a header with bitmap so this sub-allocator never returns addresses aligned on page boundary.

Here comes the first rule: if the address is not aligned on a page boundary, the block was allocated by the bitmap sub-allocator.

What about blocks bigger than one page? Yes, they can be aligned on a page boundary but how do we find allocator structures then? Of course we could simply use mmap and not bother. That's how it was done in the first version.

But this leaves us no room for creativity at this level. What if we want huge pages, how do we manage small page allocations? Huge pages aren't good for bitmap sub-allocator. What if we need to allocate from shared memory? Do that at the application level? Oh, no. That would kill the entire idea of transparent storage for data types.

Also, unlike most others, my allocator always reclaims pages back to the operating system. This does not speed up things, that's why no one reclaims. Those who do they collect free pages and use a separate low priority background thread to reclaim in one go. Too complicated solution for me. With bigger allocation blocks it's possible to reclaim entire block when all pages become free. Most likely fragmentation won't allow this, that's what I call "natural caching". But if that happens, entire big page is reclaimed in one go.

Here it is: big pages. Not huge pages to avoid confusion, but the size of big page is equal to the size of huge page. To the the smallest possible huge page, to be precise, which is typically 2 MiB.

Here comes the second rule: if the address is aligned on a page boundary, the page is allocated by page allocator and allocator structures are located at the big page boundary.

As long as this is final level of allocations, addresses can never be aligned on big page boundaries. Otherwise how do we find allocator structures?

Of course we could add a concept of "bigger" pages equal to 1 GiB huge pages but users of 32-bit system (me in the first place) won't be happy.

That's why addresses can never be aligned on big page boundaries.

Above I said I need to revise alignment rules?

I just did it. No changes. The very first small page of a big page starts from a header. The rest of that page can be used by sub-allocator.

But I need to fix the case when a block of big pages is moved. If that first page is in use, we can't remap entire big pages, we must stem another block with its own header.

Yes, it's a complication. I don't see how to make things simpler.

Actually, everything is already in place. Just needed to amend one if condition.

2026-10-04

Phew, page allocator is more complicated than bitmap sub-allocator. More execution paths, more tests to do.

Alloc and grow are ready, shrink, free, and dump to go.

Two important points that make this allocator look efficient:

  1. mremap can re-map to a reserved block of memory. Moreover, the destination may contain committed pages -- they will be freed. This behavor is described on the man page.

  2. What is more important, it's MREMAP_DONTUNMAP flag which makes possible "graceful free", keeping the memory reserved. Without this flag mremap would leave a hole in a big page. That's not good in a multi-threaded environment.

Page allocator reserves so called big pages which are equal to huge pages. Although huge pages are not used directly, I bear them in mind.

♡♡♡

The amount of good humans does not increase. The opposite is always true. It's like entropy.

Yet another -1 last weekend.

That's sad.

I tried to be nice but they didn't get it. I should not have to, wish I let my organism out to bite them, but I did not want to catch bad karma and get stuck in this shithole for next three lives.

2026-10-01

If source code produces binaries that software developers distribute to bring food on their tables, the source code is the means of production for a developer.

Open source is a way to exproptiate those means of production thus bringing software developers down to slaves and the only thing they can sell is labor.

Some may object, take open source, make binaries, sell, make money. It's like clay, sculpt anything you want. Well, clay is not free, strictly speaking. Even water is not free nowadays. Moreover, following one popular license, if you make anything from free clay, those things must be free too. The only way to make money is to sculpt free things from free clay for someone.

It's a perfect slavery!

Of course it's a shitty analogy. Developers including me love taking such analogies out of thin air. Especially from fields in which they have neither comprehension nor skills.

Anyway, it smells so.

Some jurisdictions place the equal sign between source code and literary work. That not quite correct. Literary work is consumed by readers. By humans. Source code is beyond of comprehension of most of them. It's for machines. It can be written in a human-readable way but, heck, only few are able to do that.

Just thoughts. When it came to the end I started to guess.

♡♡♡

Sometimes windows API looks more consistent than unix mess. But I don't know if windows does not behaves the same way.

In unix the memory is allocated with mmap using anonymous mappings, and pages are cleaned as expected. They contain only zeros. But what if a page was reclaimed and then committed back again?

It stays dirty and needs explicit cleaning!

Unless the mapping was destroyed by munmap and then mmaped back again.

But that's troublesome approach if we need to decommit a hole that should stay reserved. Say, we decommit a page in a reserved region. Another thread may call mmap and break everything.

A man page on madvice explains this:

MADV_FREE: The kernel can thus free these pages, but the freeing could be delayed until memory pressure occurs. For each of the pages that has been marked to be freed but has not yet been freed, the free operation will be canceled if the caller writes into the page.

So, this sequence brings the same dirty page back into the addess space:

mprotect(page, 4096, PROT_NONE);
madvise(page, 4096, MADV_FREE);
mprotect(page, 4096, PROT_READ | PROT_WRITE);

Actually, the page stayed in.

A couple of (ir)relevant links, more or less:

And as a note for myself, do not forget about madvise when you'll get to thansparent huge pages.